package com.stefan.tree;

import com.stefan.queue.LinkedListStefanQueue;
import com.stefan.queue.StefanQueue;

import java.util.LinkedList;

public class BinaryStefanTree<E> implements StefanTree<E> {
    //层次遍历
    //queue的FIFO，所以适用于树的层次遍历，先放入root，然后放入左子树，在放入右子树
    public void cengci(TreeNode<E> root) {
        LinkedList<TreeNode<E>> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode<E> treeNode = queue.poll();
            print(treeNode);
            if (treeNode.getLeft() != null) {
                queue.offer(treeNode.getLeft());
            }
            //右子树相同层的在后面
            if (treeNode.getRight() != null) {
                queue.offer(treeNode.getRight());
            }
        }
    }

    //使用我之前些的queue
    public void cengci2(TreeNode<E> root) {
        StefanQueue<TreeNode<E>> stefanQueue = new LinkedListStefanQueue<>();
        stefanQueue.enqueue(root);
        while (!stefanQueue.isEmpty()) {
            TreeNode<E> treeNode = stefanQueue.dequeue();
            print(treeNode);
            if (treeNode.getLeft() != null) {
                stefanQueue.enqueue(treeNode.getLeft());
            }
            //右子树相同层的在后面
            if (treeNode.getRight() != null) {
                stefanQueue.enqueue(treeNode.getRight());
            }
        }
    }

    public static void main(String[] args) {
        BinaryStefanTree<String> binaryStefanTree = new BinaryStefanTree();
        //构建二叉树
        TreeNode<String> d = new TreeNode<>("D",null,null);
        TreeNode<String> h = new TreeNode<>("H",null,null);
        TreeNode<String> k = new TreeNode<>("K",null,null);
        TreeNode<String> c = new TreeNode<>("C",d,null);
        TreeNode<String> g = new TreeNode<>("G",h,k);
        TreeNode<String> b = new TreeNode<>("B",null,c);
        TreeNode<String> f = new TreeNode<>("F",g,null);
        TreeNode<String> e = new TreeNode<>("E",null,f);
        TreeNode<String> a = new TreeNode<>("A",b,e);

        System.out.println("前");
        binaryStefanTree.prev(a);
        System.out.println("");
        System.out.println("中");
        binaryStefanTree.mid(a);
        System.out.println("");
        System.out.println("后");
        binaryStefanTree.after(a);
        System.out.println("");
        System.out.println("层次");
        binaryStefanTree.cengci(a);
        System.out.println("");
        System.out.println("层次2");
        binaryStefanTree.cengci2(a);
    }
}
